package com.zj.leetcode.easy.dynamicProgramming;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 比特位计数
 * 338 counting-bits
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class CountingBits {
    public static void main(String[] args) {
        int a = 16;
        Solution solution = new CountingBits().new Solution();
        System.out.println(Arrays.toString(solution.countBits01(a)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * O(n log n)
         *
         * @param n
         * @return
         */
        public int[] countBits(int n) {

            int[] ret = new int[n + 1];
            for (int i = 0; i <= n; i++) {

                int count = 0;
                int temp = i;
                while (temp > 0) {
                    if (temp % 2 == 1) {
                        count++;
                    }
                    temp = temp / 2;
                }
                ret[i] = count;
            }

            return ret;
        }

        /**
         * O(n) !!
         *
         * @param n
         * @return
         */
        public int[] countBits01(int n) {

            int[] ret = new int[n + 1];
            for (int i = 1; i <= n + 1; i++) {

                //偶数
                if((i & 1) == 0){
                    ret[i] = ret[i / 2];
                } else {
                    ret[i] = ret[i - 1] + 1;
                }
            }

            return ret;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
